#include "stack_queue.h"
using namespace std;

listNode::listNode(){
	next = NULL;
    data = 0;
}
listNode::listNode(int nodeData, listNode* succ) {
    data = nodeData;
    next = succ;
}
MyStack::MyStack(){
	topNode=NULL;
	stackSize=0;
}
MyStack::~MyStack(){
	listNode* temp;
	//从栈顶开始依次删除每个节点
	while(topNode!=NULL){
		temp=topNode;
		topNode=topNode->next;
		delete temp;
	}
}
bool MyStack::push(const int& x) {
    topNode = new listNode(x, topNode);
    stackSize++;
    return true;
}
bool MyStack::pop(int& x) {
    listNode* temp;
    if (topNode != NULL) {
        x = topNode->data;
        temp = topNode;
        topNode = topNode->next;
        delete temp;
        stackSize--;
        return true;
    }
    else {
        return false;
    }
}
bool MyStack::getTop(int& x) {
    if (topNode != NULL) {
        x = topNode->data;
        return true;
    }
    else {
        return false;
    }
}
bool MyStack::isEmpty()const
    {
        return topNode == NULL;
    }
bool MyStack::getTop(char& item)
    {
        if(topNode == NULL) return false;
        item = topNode->data;
        return true;
    }
bool MyStack::pop(char& item)
    {
        if(topNode == NULL) return false;
        item = topNode->data;
        listNode* temp = topNode;
        topNode = topNode->next;
        delete temp;
        return true;
    }
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}
MyQueue::MyQueue(const int& x) // 构造函数
    {
        capacity = x;
        queue = new int[capacity];
        front = rear = 0; // 初始化为0
    }

MyQueue::~MyQueue() {
    if (queue != nullptr) {
        delete[] queue;
        queue = nullptr;
    }
}

bool MyQueue::enQueue(const int& x) // 入队
    {
        if (isFull()) { // 如果队满，无法入队
            return false;
        } else {
            queue[rear] = x; // 将元素加入队尾
            rear = (rear + 1) % capacity; // 循环回到队头
            return true;
        }
    }
bool MyQueue::deQueue(int& x) // 出队
    {
        if (isEmpty()) { // 如果队空，无法出队
            return false;
        } else {
            x = queue[front]; // 取出队头元素
            front = (front + 1) % capacity; // 循环回到队头
            return true;
        }
    }

bool MyQueue::getFront(int& x) // 获取队头元素
    {
        if (isEmpty()) { // 如果队空，无法获取队头元素
            return false;
        } else {
            x = queue[front]; // 获取队头元素
            return true;
        }
    }

bool MyQueue::isFull() // 判断队列是否满
    {
        return ((rear + 1) % capacity == front);
    }
bool MyQueue::isEmpty() // 判断队列是否空
    {
        return (front == rear);
    }
int getOperatorPriority(const char& c){
    switch (c){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
        case ')':
            return 0;
        default:
            return -1;
    }
}
bool postfixExpression(const string& exp, string& result)
{
    result = "";
    MyStack opStack;
    bool lastIsDigit = false;

    for(int i = 0; i < exp.length(); i++){
        char c = exp[i];
        if(c >= '0' && c <= '9'){
            if(lastIsDigit)
                result += c;
            else{
                result += c;
            }
            lastIsDigit = true;
        }

        else if(c == '+' || c == '-' || c == '*' || c == '/'){
            if(opStack.isEmpty()){
                opStack.push(c);
                lastIsDigit = false;
            }
            else{
                char topOper;
                opStack.getTop(topOper);

                while(getOperatorPriority(topOper) >= getOperatorPriority(c)){
                    opStack.pop(topOper);
                    result += topOper;

                    if(opStack.isEmpty()) break;

                    opStack.getTop(topOper);
                }

                opStack.push(c);
                lastIsDigit = false;
            }
        }

        else if(c == '('){
            opStack.push(c);
            lastIsDigit = false;
        }

        else if(c == ')'){
            char topOper;
            bool findLeftBracket = false;
            while(opStack.pop(topOper)){
                if(topOper == '('){
                    findLeftBracket = true;
                    break;
                }
                result += topOper;
            }

            if(!findLeftBracket){
                result = "Expression is wrong!";
                return false;
            }

            lastIsDigit = false;
        }

        else{
            result = "Expression is wrong!";
            return false;
        }
    }

    while(!opStack.isEmpty()){
        char topOper;
        opStack.pop(topOper);

        if(topOper == '('){
            result = "Expression is wrong!";
            return false;
        }
        result += topOper;
    }
    return true;
}
bool expressionVal(const string& exp, int& result)
{
    string postExp;
    if(!postfixExpression(exp, postExp))
    {
        result = 0;
        return false;
    }

    MyStack numStack;
    for(int i = 0; i < postExp.length(); i++){
        char c = postExp[i];

        if(c == ' ') continue;

        if(c >= '0' && c <= '9'){
            int num = c - '0';
            numStack.push(num);
        }
        else if(c == '+' || c == '-' || c == '*' || c == '/'){
            if(numStack.isEmpty())
            {
                result = 0;
                return false;
            }

            int num1,num2;
            numStack.pop(num2);

            if(numStack.isEmpty())
            {
                result = 0;
                return false;
            }

            numStack.pop(num1);

            int resultNum;
            switch (c){
                case '+':
                    resultNum = num1 + num2;
                    break;
                case '-':
                    resultNum = num1 - num2;
                    break;
                case '*':
                    resultNum = num1 * num2;
                    break;
                case '/':
                    if(num2 == 0) 
                    {
                        result = 0;
                        return false;
                    }
                    resultNum = num1 / num2;
                    break;
                default:
                    result = 0;
                    return false;
            }

            numStack.push(resultNum);
        }
        else{
            result = 0;
            return false;
        }
    }

    if(numStack.isEmpty())
    {
        result = 0;
        return false;
    }

    numStack.pop(result);

    if(!numStack.isEmpty())
    {
        result = 0;
        return false;
    }

    return true;
}
void yanghui(const int& num_rows) {
    MyQueue q(100); // capacity set to 100

    // Enqueue the first row
    q.enQueue(1);

    // Loop through each row of the triangle
    for (int i = 1; i <= num_rows; ++i) {
        int prev = 0;

        // Dequeue the previous row and enqueue the next row
        for (int j = 0; j < i; ++j) {
            int curr;
            q.deQueue(curr);
            q.enQueue(curr + prev);
            prev = curr;
        }

        // Add the final 1 to the end of the row
        q.enQueue(1);

        // Print the row
        q.printQueue();
    }
}



